In a software configuration management (SCM) system, users describe how to build software systems. The notation for such descriptions varies between SCM systems. In one notation used by the invention described below, the instructions take the form of a program written in a functional language. The program specifies how to build the software from scratch, that is, source files. In the functional program, invocations of external tools like compilers and linkers are written as function calls. Because the program specifies how to build the software from scratch, results from previous builds an be remembered and reused to achieve good incremental performance. Typically, the results are stored in a cache.
In a prior art SCM system, a function cache is also used. U.S. Pat. No. 5,500,881, "Language Scoping for Modular, Concise, Configuration Descriptions," issued to Levin et al on Mar. 19, 1996, see also "The Vesta Approach to Precise Configuration of Large Software," Levin et al, SRC Research Report 105, June, 1993, http://gatekeeper.dec.com/pub/DEC/SRC/-research-reports/abstracts/src-rr-1 05.html, "The Vesta Repository: A File System Extension for Software Development," Chiu et al., SRC Research Report 106, June, 1993, http://gatekeeper.dec.com/pub/DEC/-SRC/research-reports/abstracts/src-rr-1 06.html, "The Vesta Language for Configuration Management," Hanna et al., SRC Research Report 107, June, 1993, http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/src-rr-10 7.html, and "Bridges: Tools to Extend the Vesta Configuration Management System," Brown et al., SRC Research Report 108, June, 1993, http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/src-rr-10 8.html.
The primary operations performed by a function cache are AddEntry and Lookup. Entries, according to Vesta, are indexed by primary and secondary keys. AddEntry places results in the function cache, and Lookup retrieves entries (hits), or produces misses if there is no corresponding entry for the Lookup key.
The function cache in the prior art differs from what is disclosed below in two aspects. First, the function cache in the prior art only considers a subset of the existing cache entries. Hence, caching is not always completely accurate: it is possible to get a false miss on the cache. Second, the entries in the prior art cache are partitioned only into groups with the same primary key. Hence, the Lookup operation with that function cache has to consider every secondary dependency name of every cache entry in the relevant primary key (PK) group. These terms are described in greater detail below.
The ClearCASE product formerly of Atria Software Inc, now from Pure Software Inc, is another software configuration management system that caches builds, but apparently ClearCASE uses a slow, brute-force approach that requires comparing the versions of all the dependencies to all of a tool application's potential cache entries, "ClearCASE Concepts Manual," Atria Software, Inc., 1992.
Therefore, it is desired to provide an efficient function cache that stores dynamic, fine-grained dependencies.